13.8 KB · ⇊ 4 parts · ⤓ Micron 13.8 KB · ⤓ HTML 102.2 KB

top

In der linearen Algebra ist eine Givens-Rotation (nach Wallace Givens) eine Drehung in einer Ebene, die durch zwei Koordinaten-Achsen aufgespannt wird. Manchmal wird dies auch als Jacobi-Rotation (nach Carl Gustav Jacobi) bezeichnet.

Die Anwendung als Methode in der numerischen linearen Algebra zum Beispiel bei der Bestimmung von Eigenwerten und QR-Zerlegung stammt aus den 1950er Jahren, als Givens am Oak Ridge National Laboratory war. Solche Drehungen werden schon im älteren Jacobi-Verfahren (1846) benutzt, praktikabel wurden sie allerdings erst mit dem Aufkommen von Computern.

• Beschreibung

• QR-Zerlegung mittels Givens-Rotationen

• Beispiel

• Algorithmus

• Verallgemeinerung

• Literatur

• Anmerkungen

Die Transformation lässt sich durch eine orthogonale Matrix der Form

G ( i , k , θ θ ) = [ 1 ⋯ ⋯ 0 ⋯ ⋯ 0 ⋯ ⋯ 0 ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 ⋯ ⋯ c ⋯ ⋯ − − s ⋯ ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ 0 ⋯ ⋯ s ⋯ ⋯ c ⋯ ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ 0 ⋯ ⋯ 0 ⋯ ⋯ 0 ⋯ ⋯ 1 ] {\displaystyle G(i,k,\theta )={\begin{bmatrix}1&\cdots &0&\cdots &0&\cdots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\cdots &c&\cdots &-s&\cdots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\cdots &s&\cdots &c&\cdots &0\\\vdots &&\vdots &&\vdots &\ddots &\vdots \\0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}}}

beschreiben, wobei c = cos ⁡ ⁡ ( θ θ ) {\displaystyle c=\cos(\theta )} und s = sin ⁡ ⁡ ( θ θ ) {\displaystyle s=\sin(\theta )} in der i {\displaystyle i} -ten und k {\displaystyle k} -ten Zeile und Spalte erscheinen. Eine solche Matrix heißt Givens-Matrix. Formaler ausgedrückt:

G ( i , k , θ θ ) j , l = { cos ⁡ ⁡ θ θ falls j = i , l = i oder j = k , l = k sin ⁡ ⁡ θ θ falls j = i , l = k − − sin ⁡ ⁡ θ θ falls j = k , l = i 1 falls j = l , j ≠ ≠ i , j ≠ ≠ k 0 sonst. {\displaystyle G(i,k,\theta )_{j,l}={\begin{cases}\cos \theta &{\mbox{ falls }}j=i,l=i{\mbox{ oder }}j=k,l=k\\\sin \theta &{\mbox{ falls }}j=i,l=k\\-\sin \theta &{\mbox{ falls }}j=k,l=i\\1&{\mbox{ falls }}j=l,j\neq i,j\neq k\\0&{\mbox{ sonst. }}\end{cases}}}

Das Matrix-Vektor-Produkt G T ( i , k , θ θ ) x {\displaystyle G^{T}(i,k,\theta )x} stellt eine Drehung (gegen den Uhrzeigersinn) des Vektors x {\displaystyle x} um einen Winkel θ θ {\displaystyle \theta } in der ( i , k ) {\displaystyle (i,k)} -Ebene dar, diese wird Givens-Rotation genannt.

Die Hauptanwendung der Givens-Rotation liegt in der numerischen linearen Algebra, um Nulleinträge in Vektoren und Matrizen zu erzeugen. Dieser Effekt kann beispielsweise bei der Berechnung der QR-Zerlegung einer Matrix ausgenutzt werden. Außerdem werden solche Drehmatrizen beim Jacobi-Verfahren benutzt.

• Das Verfahren ist stabil. Pivotisierung ist nicht erforderlich.

• Flexible Berücksichtigung von schon vorhandenen 0-Einträgen in strukturierten (insbesondere dünnbesetzten) Matrizen.

• Die Idee besteht darin, sukzessiv die Elemente unterhalb der Hauptdiagonalen auf Null zu setzen, indem man die Matrix von links mit Givens-Rotationen multipliziert. Zunächst bearbeitet man die erste Spalte von oben nach unten und dann nacheinander die anderen Spalten ebenfalls von oben nach unten.

• Man muss also O ( m n ) {\displaystyle {\mathcal {O}}(m\,n)} Matrizenmultiplikationen durchführen. Da sich jeweils pro Multiplikation höchstens 2n Werte verändern, beträgt der Aufwand für eine QR-Zerlegung einer vollbesetzten m×n-Matrix insgesamt O ( m n 2 ) {\displaystyle {\mathcal {O}}(m\,n^{2})} . Für dünn besetzte Matrizen ist der Aufwand allerdings erheblich niedriger.

• Will man den Eintrag an der Matrixposition ( i , j ) {\displaystyle (i,j)} zu null transformieren, so setzt man c = a j j / ρ ρ {\displaystyle c=a_{jj}/\rho } und s = a i j / ρ ρ {\displaystyle s=a_{ij}/\rho } , wobei ρ ρ = sgn ⁡ ⁡ ( a j j ) a j j 2 + a i j 2 {\displaystyle \rho =\operatorname {sgn}(a_{jj}){\sqrt {a_{jj}^{2}+a_{ij}^{2}}}} .

G 2 , 4 ⋅ ⋅ G 1 , 4 ⋅ ⋅ [ 3 5 0 2 0 0 4 5 ] = G 2 , 4 ⋅ ⋅ [ 5 7 0 2 0 0 0 − − 1 ] = [ 5 7 0 5 0 0 0 0 ] {\displaystyle G_{2,4}\cdot G_{1,4}\cdot {\begin{bmatrix}3&5\\0&2\\0&0\\4&5\end{bmatrix}}=G_{2,4}\cdot {\begin{bmatrix}5&7\\0&2\\0&0\\0&-1\end{bmatrix}}={\begin{bmatrix}5&7\\0&{\sqrt {5}}\\0&0\\0&0\end{bmatrix}}}

mit

G 1 , 4 = [ 3 5 0 0 4 5 0 1 0 0 0 0 1 0 − − 4 5 0 0 3 5 ] {\displaystyle G_{1,4}={\begin{bmatrix}{\frac {3}{5}}&0&0&{\frac {4}{5}}\\0&1&0&0\\0&0&1&0\\-{\frac {4}{5}}&0&0&{\frac {3}{5}}\end{bmatrix}}} , G 2 , 4 = [ 1 0 0 0 0 2 5 0 − − 1 5 0 0 1 0 0 1 5 0 2 5 ] {\displaystyle G_{2,4}={\begin{bmatrix}1&0&0&0\\0&{\frac {2}{\sqrt {5}}}&0&-{\frac {1}{\sqrt {5}}}\\0&0&1&0\\0&{\frac {1}{\sqrt {5}}}&0&{\frac {2}{\sqrt {5}}}\\\end{bmatrix}}}

Man erhält schließlich die QR-Zerlegung:

Q = ( G 2 , 4 ⋅ ⋅ G 1 , 4 ) T = ( G 1 , 4 T ⋅ ⋅ G 2 , 4 T ) = [ 3 5 4 5 5 0 − − 8 5 5 0 2 5 0 1 5 0 0 1 0 4 5 − − 3 5 5 0 6 5 5 ] , R = [ 5 7 0 5 0 0 0 0 ] , Q ⋅ ⋅ R = [ 3 5 0 2 0 0 4 5 ] {\displaystyle Q=(G_{2,4}\cdot G_{1,4})^{T}=(G_{1,4}^{T}\cdot G_{2,4}^{T})={\begin{bmatrix}{\frac {3}{5}}&{\frac {4}{5{\sqrt {5}}}}&0&-{\frac {8}{5{\sqrt {5}}}}\\0&{\frac {2}{\sqrt {5}}}&0&{\frac {1}{\sqrt {5}}}\\0&0&1&0\\{\frac {4}{5}}&-{\frac {3}{5{\sqrt {5}}}}&0&{\frac {6}{5{\sqrt {5}}}}\end{bmatrix}},\quad R={\begin{bmatrix}5&7\\0&{\sqrt {5}}\\0&0\\0&0\end{bmatrix}},\quad Q\cdot R={\begin{bmatrix}3&5\\0&2\\0&0\\4&5\end{bmatrix}}}

Zur Berechnung einer QR-Zerlegung einer Matrix A = ( a i , j ) i , j ∈ ∈ R m × × n , m ≥ ≥ n {\displaystyle A=\left(a_{i,j}\right)_{i,j}\in \mathbb {R} ^{m\times n},m\geq n} geht man wie folgt vor.

Drehe die erste Spalte a − − , 1 {\displaystyle a_{-,1}} der Matrix A {\displaystyle A} auf einen Vektor mit einer Null als letzten Eintrag:

G 1 , m A = [ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ ⋮ ⋮ ⋱ ⋱ ⋱ ⋱ ⋮ ⋮ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 ∗ ∗ ⋯ ⋯ ∗ ∗ ] {\displaystyle G_{1,m}A={\begin{bmatrix}*&\cdots &\cdots &*\\\vdots &\ddots &\ddots &\vdots \\*&\cdots &\cdots &*\\0&*&\cdots &*\end{bmatrix}}}

wobei c , s , ρ ρ {\displaystyle c,s,\rho } für G 1 , m {\displaystyle G_{1,m}} wie oben beschrieben gewählt werden müssen:

ρ ρ = sgn ⁡ ⁡ ( a 1 , 1 ) a 1 , 1 2 + a m , 1 2 , c = a 1 , 1 ρ ρ , s = a m , 1 ρ ρ . {\displaystyle \rho =\operatorname {sgn}(a_{1,1}){\sqrt {a_{1,1}^{2}+a_{m,1}^{2}}},\;c={\frac {a_{1,1}}{\rho }},\;s={\frac {a_{m,1}}{\rho }}.}

Nun geht man analog mit den nächsten Einträgen der ersten Spalte vor und speichert sich alle Umformungsmatrizen G 1 , i , i = 2 , … … , m {\displaystyle G_{1,i},i=2,\ldots ,m} in der Matrix G 1 {\displaystyle G_{1}} :

G 1 A = [ ∗ ∗ ⋯ ⋯ ⋯ ⋯ ∗ ∗ 0 ∗ ∗ ⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ ⋮ ⋮ 0 ∗ ∗ ⋯ ⋯ ∗ ∗ ] mit G 1 := G 1 , 2 ⋅ ⋅ … … ⋅ ⋅ G 1 , m . {\displaystyle {\begin{aligned}G_{1}A=&{\begin{bmatrix}*&\cdots &\cdots &*\\0&*&\ddots &\vdots \\\vdots &\vdots &\ddots &\vdots \\0&*&\cdots &*\end{bmatrix}}\\{\text{mit}}\quad G_{1}:=&G_{1,2}\cdot \ldots \cdot G_{1,m}.\end{aligned}}}

Dabei muss unbedingt darauf geachtet werden, dass sich die einzelnen Einträge ( c , s , ρ ρ ) {\displaystyle (c,s,\rho )} der Matrizen G 1 , i {\displaystyle G_{1,i}} nicht mehr auf die ursprüngliche Matrix A {\displaystyle A} beziehen, sondern auf die schon umgeformte Matrix: G 1 , i + 1 ⋅ ⋅ … … ⋅ ⋅ G 1 , m A {\displaystyle G_{1,i+1}\cdot \ldots \cdot G_{1,m}A} .

Nun muss man die folgenden Spalten analog bearbeiten und somit Umformungsmatrizen G i , i = 2 , … … , n {\displaystyle G_{i},i=2,\ldots ,n} finden, welche jeweils die i {\displaystyle i} -te Spalte der Matrix G i − − 1 ⋅ ⋅ … … ⋅ ⋅ G 1 A {\displaystyle G_{i-1}\cdot \ldots \cdot G_{1}A} auf einen Vektor mit Nulleinträgen unterhalb des i {\displaystyle i} -ten Elements transformiert.

Schlussendlich ergibt sich die QR-Zerlegung mittels:

Q := G 1 T ⋅ ⋅ … … ⋅ ⋅ G n T und R := G n ⋅ ⋅ … … ⋅ ⋅ G 1 A . {\displaystyle Q:=G_{1}^{T}\cdot \ldots \cdot G_{n}^{T}\quad {\text{und}}\quad R:=G_{n}\cdot \ldots \cdot G_{1}A.}

In drei Dimensionen gibt es 3 Givens-Rotationen:

R X ( θ θ ) = ( 1 0 0 0 cos ⁡ ⁡ θ θ − − sin ⁡ ⁡ θ θ 0 sin ⁡ ⁡ θ θ cos ⁡ ⁡ θ θ ) {\displaystyle R_{X}(\theta )={\begin{pmatrix}1&0&0\\0&\cos \theta &-\sin \theta \\0&\sin \theta &\cos \theta \end{pmatrix}}}

R Y ( θ θ ) = ( cos ⁡ ⁡ θ θ 0 − − sin ⁡ ⁡ θ θ 0 1 0 sin ⁡ ⁡ θ θ 0 cos ⁡ ⁡ θ θ ) {\displaystyle R_{Y}(\theta )={\begin{pmatrix}\cos \theta &0&-\sin \theta \\0&1&0\\\sin \theta &0&\cos \theta \end{pmatrix}}} cite-ref-1[Anmerkung 1]

R Z ( θ θ ) = ( cos ⁡ ⁡ θ θ − − sin ⁡ ⁡ θ θ 0 sin ⁡ ⁡ θ θ cos ⁡ ⁡ θ θ 0 0 0 1 ) {\displaystyle R_{Z}(\theta )={\begin{pmatrix}\cos \theta &-\sin \theta &0\\\sin \theta &\cos \theta &0\\0&0&1\end{pmatrix}}}

Diese 3 zusammengesetzten Givens-Rotationen können jede Drehmatrix nach dem Davenport's chained rotation theorem erzeugen. Dies bedeutet, dass sie die Standardbasis des Vektorraums in jede andere Basis im Vektorraum umwandeln können.

• Gene H. Golub, Charles F. van Loan: Matrix Computations. 2nd Edition. The Johns Hopkins University Press, 1989.

• Martin Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage, Walter de Gruyter Verlag, Berlin und Boston 2020, ISBN 978-3-11-065665-7.

• W. Dahmen, A. Reusken: Numerik für Ingenieure und Naturwissenschaftler. Springer-Verlag Berlin Heidelberg, 2006, ISBN 3-540-25544-3

cite-note-1Anmerkung 1. ↑ Die R Y ( θ θ ) {\displaystyle R_{Y}(\theta )} Matrix direkt unterhalb ist keine Givens-Rotation. Die R Y ( θ θ ) {\displaystyle R_{Y}(\theta )} -Matrix direkt unterhalb befolgt die Rechte-Hand-Regel und wird üblicherweise in der Computergrafik verwendet. Eine Givens-Rotation ist jedoch einfach eine Matrix gemäß Definition im Abschnitt Beschreibung oben und befolgt nicht zwingend die Rechte-Hand-Regel. Die Matrix unterhalb zeigt tatsächlich die Givens-Rotation um einen Winkel - θ θ {\displaystyle \theta } . R Y ( θ θ ) = [ cos ⁡ ⁡ θ θ 0 sin ⁡ ⁡ θ θ 0 1 0 − − sin ⁡ ⁡ θ θ 0 cos ⁡ ⁡ θ θ ] {\displaystyle R_{Y}(\theta )={\begin{bmatrix}\cos \theta &0&\sin \theta \\0&1&0\\-\sin \theta &0&\cos \theta \end{bmatrix}}}